Compression and encoding technology is used in order to transmit and store still image data and moving image data with good efficiency. In the case of moving images, the methods MPEG-1 to 4 or ITU (International Telecommunication Union) H.261 to H.264 are widely used.
In encoding methods of this kind, encoding and decoding processes are carried out by dividing the image that is the object of encoding into a plurality of blocks. In predictive encoding within a frame, a prediction signal is generated by using an already reproduced image signal (compressed image data that has been decompressed) which is situated adjacently within the same frame as the object block, and the differential signal obtained by subtracting this prediction signal from the signal of the object block is encoded. In predictive encoding between frames, a prediction signal is generated by referring to an already reproduced image signal which is situated adjacently in a different frame to the object block and performing movement correction, and the differential signal obtained by subtracting this prediction signal from the signal of the object block is encoded.
For example, H.264 intra-frame predictive encoding uses a method where a prediction signal is generated by extrapolating already reproduced pixel values which are situated adjacently to the block which is the object of encoding, in a prescribed direction. FIGS. 18A to 18I are schematic drawings for describing an intra-frame prediction method which is used in ITU H.264. In FIG. 18A, the object block 1802 is the block which is the object of encoding, and the pixel group 1801 consisting of pixels A to M which are situated adjacently to the boundaries of this object block 1802 is the adjacent region, which is an image signal that has already been reproduced in a previous processing step.
In this case, a prediction signal is generated by extrapolating downwards the pixel group 1801 consisting of adjacent pixels which are situated directly above the object block 1802. Furthermore, in FIG. 18B, a prediction signal is generated by extrapolating rightwards the already reproduced pixels (I to L) which are situated to the left of the object block 1804. The actual method of generating the prediction signal is described in Patent Document 1, for example. The differential with respect to the pixel signal of the object block is found for each of the nine respective prediction signals generated by the methods shown in FIGS. 18A to 18I in this way, and the prediction signal having the smallest differential is taken to be the optimal prediction signal. As described above, in this way, it is possible to generate a prediction signal by extrapolating pixels. The contents described above are explained in Patent Document 1.
In normal predictive encoding between frames, a prediction signal is generated by a method which searches for and finds a signal resembling the pixel signal of the block that is the object of encoding, from amongst frames which have already been reproduced. A motion vector which indicates the amount of spatial displacement between the object block and the region constituted by the selected signal is encoded together with the residual signal between the pixel signal of the object block and the prediction signal. The technique of searching for a motion vector for each block in this way is called block matching.
FIG. 4 is a schematic drawing for describing a block matching process. Here, the procedure for generating a prediction signal will be described by taking as an example the object block 402 of the frame 401 which is the object of encoding. The frame 403 has already been reproduced, and the region 404 is a region which is in the same spatial position as the object block 402. In block matching, a search range 405 surrounding the region 404 is established, and the region 406 having the smallest sum of absolute differences between the pixel signal of the search range and the pixel signal of the object block 402 is determined. The signal of this region 406 becomes the prediction signal, and the amount of displacement from the region 404 to the region 406 is determined as the motion vector 407. In H.264, in order to correspond to characteristic local changes in the image, a plurality of prediction types having different block sizes are prepared for encoding the motion vector. The prediction types in H.264 are described in Patent Document 2, for example.
In compression encoding of moving image data, the respective frames can be encoded in any desired sequence. Therefore, there are three different methods in terms of the encoding sequence which can be employed in inter-frame prediction for generating prediction signals by referring to already reproduced frames. The first method is forward prediction which generates a prediction signal by referring to an already reproduced frame which is in the past in the reproduction sequence, the second method is backward prediction which refers to an already reproduced frame which is in the future in the reproduction sequence, and the third method is bidirectional prediction which carries out both forward prediction and backward prediction and finds the average of the two prediction signals. The types of inter-frame prediction are described in Patent Document 3, for example.    Patent Document 1: U.S. Pat. No. 6,765,964    Patent Document 2: U.S. Pat. No. 7,003,035    Patent Document 3: U.S. Pat. No. 6,259,739